package com.zrrd.zuo.dp;

import java.util.HashMap;

/**
 * @author ywb
 * @Description:
 * @date 2023/4/19 14:02
 */
public class StickWord {
    //1.暴力 超时
    public int minStickers(String[] stickers, String target) {
        int ans = process1(stickers, target);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
    public static int process1(String[] stickers,String target)
    {
        if(target.length() == 0){
            return 0;
        }
        int min = Integer.MAX_VALUE;
        for(String s : stickers){
            String path = minus(target,s);
            if(path.length() != target.length()){
                min = Math.min(min, process1(stickers, path));
            }
        }
        return min + (min == Integer.MAX_VALUE ? 0 : 1);
    }
    public static String minus(String target,String s){
        char[] str1 = target.toCharArray();
        char[] str2 = s.toCharArray();
        int[] c = new int[26];
        for(char a : str1){
            c[a - 'a']++;
        }
        for(char a : str2){
            c[a - 'a']--;
        }
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < 26; i++) {
            if (c[i] > 0) {
                for (int j = 0; j < c[i]; j++) {
                    builder.append((char) (i + 'a'));
                }
            }
        }
        return builder.toString();
    }
    //2.剪枝暴力 字母表代替 超时
    public int minStickers1(String[] stickers, String target) {
        int[][] count = new int[stickers.length][26];
        for (int i = 0; i < stickers.length; i++) {
            char[] c = stickers[i].toCharArray();
            for (int j = 0; j < c.length; j++) {
                count[i][c[j] - 'a']++;
            }
        }
        int ans = process2(count, target);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
    public static int process2(int[][] stickers,String t)
    {
        if(t.length() == 0){
            return 0;
        }
        char[] target = t.toCharArray();
        int[] tcounts = new int[26];
        for (char cha : target) {
            tcounts[cha - 'a']++;
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < stickers.length; i++) {
            //剪枝
            if(stickers[i][tcounts[0] - 'a']>0){
                StringBuilder builder = new StringBuilder();
                for (int j = 0; j < 26; j++) {
                    if (tcounts[j] > 0) {
                        int nums = tcounts[j] - stickers[i][j];
                        for (int k = 0; k < nums; k++) {
                            builder.append((char) (j + 'a'));
                        }
                    }
                }
                String rest = builder.toString();
                min = Math.min(min, process2(stickers, rest));
            }
        }
        return min + (min == Integer.MAX_VALUE ? 0 : 1);
    }
    public static String minus2(String target,String s){
        char[] str1 = target.toCharArray();
        char[] str2 = s.toCharArray();
        int[] c = new int[26];
        for(char a : str1){
            c[a - 'a']++;
        }
        for(char a : str2){
            c[a - 'a']--;
        }
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < 26; i++) {
            if (c[i] > 0) {
                for (int j = 0; j < c[i]; j++) {
                    builder.append((char) (i + 'a'));
                }
            }
        }
        return builder.toString();
    }
    //加入dp记忆搜索缓存
    public static int minStickers3(String[] stickers, String target) {
        int N = stickers.length;
        int[][] counts = new int[N][26];
        for (int i = 0; i < N; i++) {
            char[] str = stickers[i].toCharArray();
            for (char cha : str) {
                counts[i][cha - 'a']++;
            }
        }
        HashMap<String, Integer> dp = new HashMap<>();
        dp.put("", 0);
        int ans = process3(counts, target, dp);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    public static int process3(int[][] stickers, String t, HashMap<String, Integer> dp) {
        if (dp.containsKey(t)) {
            return dp.get(t);
        }
        char[] target = t.toCharArray();
        int[] tcounts = new int[26];
        for (char cha : target) {
            tcounts[cha - 'a']++;
        }
        int N = stickers.length;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < N; i++) {
            int[] sticker = stickers[i];
            if (sticker[target[0] - 'a'] > 0) {
                StringBuilder builder = new StringBuilder();
                for (int j = 0; j < 26; j++) {
                    if (tcounts[j] > 0) {
                        int nums = tcounts[j] - sticker[j];
                        for (int k = 0; k < nums; k++) {
                            builder.append((char) (j + 'a'));
                        }
                    }
                }
                String rest = builder.toString();
                min = Math.min(min, process3(stickers, rest, dp));
            }
        }
        int ans = min + (min == Integer.MAX_VALUE ? 0 : 1);
        dp.put(t, ans);
        return ans;
    }
}
